package main

import (
	"container/list"
	"fmt"
	"sync"
)

//定义一个栈
type Stack struct {
	list *list.List
	//为保证读写安全加个锁
	lock *sync.RWMutex
}

//初始化栈
func NewStack() *Stack {
	list := list.New()
	lock := &sync.RWMutex{}
	return &Stack{list, lock}
}

//将数据存入
func (stack *Stack) Push(value interface{}) {
	//加写锁
	stack.lock.Lock()
	//延迟解锁
	defer stack.lock.Unlock()
	//存入数据
	stack.list.PushBack(value)
}

//将数据出栈
func (stack *Stack) Pop() interface{} {
	//加写锁
	stack.lock.Lock()
	//延迟解锁
	defer stack.lock.Unlock()
	tail := stack.list.Back()
	if tail == nil {
		return nil
	} else {
		stack.list.Remove(tail)
		return tail.Value
	}
}

func (stack *Stack) Peek() interface{} {
	stack.lock.Lock()
	defer stack.lock.Unlock()
	tail := stack.list.Back()
	if tail == nil {
		return nil
	} else {
		return tail.Value
	}
}

func (stack *Stack) Len() int {
	stack.lock.RLock()
	defer stack.lock.RUnlock()
	return stack.list.Len()
}

func (stack *Stack) Traverse() {
	stack.lock.RLock()
	defer stack.lock.RUnlock()
	//反向遍历链表
	ReverseList(stack.list)
}

type StackNode struct {
	value interface{}
	prev  *StackNode
}

type MyStack struct {
	top    *StackNode
	length int
	lock   *sync.RWMutex
}

func NewMyStack() *MyStack {
	return &MyStack{nil, 0, &sync.RWMutex{}}
}

func (stack *MyStack) Push(value interface{}) {
	stack.lock.Lock()
	defer stack.lock.Unlock()
	node := &StackNode{value: value, prev: stack.top}
	stack.top = node
	stack.length += 1
}

func (stack *MyStack) Pop() interface{} {
	stack.lock.Lock()
	stack.lock.Unlock()
	if stack.length == 0 {
		return nil
	}
	top := stack.top
	blow := top.prev
	stack.top = blow
	stack.length--

	return top.value
}

func (stack *MyStack) Traverse() {
	stack.lock.RLock()
	defer stack.lock.RUnlock()
	curr := stack.top
	for curr != nil {
		fmt.Printf("%v", curr.value)
		curr = curr.prev
	}
	fmt.Println()
}

func main() {
	s1 := NewStack()
	s1.Push(1)
	s1.Push(2)
	s1.Pop()
	fmt.Println("=============")
	s2 := NewMyStack()
	s2.Push(1)
	s2.Push(2)
	s2.Push(3)
	s2.Pop()
	s2.Traverse()

}
